package problem673;

//673.最长递增子序列的个数
//https://leetcode.cn/problems/number-of-longest-increasing-subsequence/

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        int[] len = new int[n];
        int[] count = new int[n];
        for(int i = 0; i<n; i++) {
            len[i] = 1;
            count[i] = 1;
        }
        for(int i = 1; i<n; i++) {
            for(int j = i-1; j>=0; j--) {
                if(nums[j] < nums[i]) {
                    if(len[j] + 1 > len[i]) {
                        len[i] = len[j]+1;
                        count[i] = count[j];
                    }else if(len[j] + 1 == len[i]) {
                        count[i] += count[j];
                    }
                }
            }
        }

        //返回结果
        int maxLen = 0;
        int ret = 0;
        for(int i = 0; i<n; i++) {
            System.out.print(count[i] + " ");
            if(maxLen == len[i]) {
                ret += count[i];
            }else if(maxLen < len[i]) {
                maxLen = len[i];
                ret = count[i];
            }
        }
        return ret;
    }
}

/*
len[i]:以第i个元素为结尾的最长递增子序列的长度
count[i]:以第i个元素为结尾的最长递增子序列的个数
*/